package toOffer
/*
	给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动k个位置。

	示例 1：


	输入：head = [1,2,3,4,5], k = 2
	输出：[4,5,1,2,3]
	示例 2：


	输入：head = [0,1,2], k = 4
	输出：[2,0,1]

	提示：

	链表中节点的数目在范围 [0, 500] 内
	-100 <= Node.val <= 100
	0 <= k <= 2 * 109

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/rotate-list
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
type ListNode struct {
	Val  int
	Next *ListNode
}

func rotateRight(head *ListNode, k int) *ListNode {
	if nil == head {
		return head
	}
	// 1. 求出链表长度 size
	size := getSize(head)
	// 2. 将链表变成一个环
	oldHead := head
	cur := head
	for cur.Next != nil {
		cur = cur.Next
	}
	cur.Next = head
	// 3. 给定一个指针cur指向链表当前头节点、后移size-k%size步、cur.Next即是新的头节点
	for i := 1; i < size-k%size; i++ {
		oldHead = oldHead.Next
	}
	newHead := oldHead.Next
	// 4. 断开cur与cur.Next的链接
	oldHead.Next = nil
	return newHead
}

func getSize(head *ListNode) int {
	cur := head
	size := 0
	for cur != nil {
		size++
		cur = cur.Next
	}
	return size
}
